package Elementary_algorithm.DynamicProgramming;

import org.junit.Test;

/*
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
    偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
    偷窃到的最高金额 = 2 + 9 + 1 = 12 。

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnq4km/
 */
public class _04打家劫舍 {

    @Test
    public void test(){
        System.out.println(rob2(new int[]{1,2,3,1}));
    }


    //WA
    //没有考虑到[2,1,1,2] 答案因为4
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        int maxProfit = 0;
        int profit1 = 0;
        int profit2 = 0;
        int i = 0,j = 1;
        while (i < nums.length || j < nums.length) {
            if (i < nums.length ) {
                profit1 += nums[i];
            }
            if (j < nums.length) {
                profit2 += nums[j];
            }
            i = i + 2;
            j = j + 2;
        }
        maxProfit = Math.max(profit1, profit2);
        return maxProfit;
    }

    //DP + 滚动数组
    //f(n) = max( f(n-1) , f(n - 2) + n)
    //ps: 跟昨天爬楼梯很像
    // 官方的思路:
    // 如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第k(k>2)间房屋，有两个选项：
    // 1.偷窃第k间房屋，那么就不能偷窃第k−1间房屋，偷窃总金额为前k−2间房屋的最高总金额与第k间房屋的金额之和。
    // 2.不偷窃第k间房屋，偷窃总金额为前k−1间房屋的最高总金额。
    // 我的思路:
    // 设f(n)为以数组第n个房间为结尾的最大偷窃金额，然后去思考f(n)改怎么跟前面的房间联系起来
    // 很自然想到若不偷窃第n个房间，那么其为f(n) = f(n-1)
    // 那若偷窃呢？  那么第n-1个房间就不能偷窃了 ==> f(n-1)就用不了,思考f(n-2) ==> 推测f(n) = f(n-2) + n
    // 于是有了f(n) = max( f(n-1) , f(n - 2) + n)  , 带入例子测试，AC
    //ps2: 因为f(n) 只跟 f(n-1)和f(n-2) 有关，故可以采用滚动数组思想，将O(n) 降低为 O(1)
    public int rob2(int[] nums) {
        if(nums.length == 1) return nums[0];
        int p = 0,q = 0,r = 0;
        for (int i = 0; i < nums.length; i++) {
            p = q;
            q = r;
            r = Math.max(p + nums[i], q);
        }
        return r;
    }

    //官解：方法一：动态规划
    class Solution {
        public int rob(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int length = nums.length;
            if (length == 1) {
                return nums[0];
            }
            int first = nums[0], second = Math.max(nums[0], nums[1]);
            for (int i = 2; i < length; i++) {
                int temp = second;
                second = Math.max(first + nums[i], second);
                first = temp;
            }
            return second;
        }
    }

}
